//
// Created by postgres on 6/23/17.
//
#include "../include/08search/BTreePlus.h"

#define N 20 /*  数据元素个数 */
#define even_number max_degree%2
#if even_number
   #define MiddleKey (max_degree+1)/2;
#else
  #define MiddleKey (max_degree+1)/2+1;
#endif

#define MinKeyNum (max_degree+1)/2-1;
#define MaxKeyNum max_degree-1;
/*-----------------------------------------Search--------------------------------------------*/
//寻找在本节点中应该插入的位置
int SearchPosition(BTreePlus T, KeyType k) {
    int i = 1, n = T->keynum;
    while (i <= n && T->data[i] <= k)
        i++;
    return i - 1;
}
RSet find_leaf(BTreePlus T, KeyType k){
    BTreePlus p = T, q;
    int i = 0, found = 0;
    RSet r;
    while (p && !found) {
        i = SearchPosition(p, k);
        if (i > 0 && p->data[i] == k&&p->is_leaf)
            found = 1;
        else {
            q = p;
            p = p->child[i];
        }
    }
    if (found) {
        r.node = p;
        r.flag = 1;
        r.pos = i;
    } else {
        r.node = q;
        r.flag = 0;
        r.pos = i;
    }
    return r;
}
//循环查找直到叶子为止.如果找到就返回待插入节点、插入位置,找到标记flag为1
RSet find_node(BTreePlus T, KeyType k) {
    BTreePlus p = T, q;
    int i = 0, found = 0;
    RSet r;
    while (p && !found) {
        i = SearchPosition(p, k);
        if (i > 0 && p->data[i] == k)
            found = 1;
        else {
            q = p;
            p = p->child[i];
        }
    }
    if (found) {
        r.node = p;
        r.flag = 1;
        r.pos = i;
    } else {
        r.node = q;
        r.flag = 0;
        r.pos = i;
    }
    return r;
}
/*-----------------------------------------Delete--------------------------------------------*/
//查找中序的后继节点：向右然后一路向左，就能找到前驱节点
RSet find_next_key(BTreePlus t,int pos){

    BTreePlus p;
    RSet r;
    r.pos=-1;
    r.null_child_index=-1;
    r.flag=-1;
    if(!t)return r;
    p=t;
    p=p->child[pos];
    while(p->child[0]){
        p=p->child[0];
    }
    r.pos=1;
    r.node=p;
    r.flag=TRUE;
    return r;
}
//查找中序的后继节点：向右然后一路向左，就能找到前驱节点
/**
 *
 * @param leaf :leaf node
 * @param pos: position of key
 * @return
 */
ResKey next_key(BTreePlus leaf,int pos){
    BTreePlus p;
    ResKey k;
    k.key=KeyType_NULL;
    k.flag=FALSE;
    p=leaf;
    if(pos<p->keynum){
        k.key=leaf->data[pos+1];
        k.flag=TRUE;
    }
    else if(pos==p->keynum&&p->next){
        p=p->next;
        k.key=p->data[1];
        k.flag=TRUE;
    }
    return k;
}
void adjust_parent_index(BTreePlus *parent){
    int i;
    for(i=1;i<=(*parent)->keynum;i++){
        (*parent)->data[i]=(*parent)->child[i]->data[1];
    }

}
void adjust_node_index(BTreePlus *node,int before_num){
    int i;
    if(before_num<=0)before_num=1;
    for(i=before_num;i<=(*node)->keynum;i++){
        (*node)->data[i]=(*node)->child[i]->data[1];
    }

}
void replace_key(BTreePlus root,KeyType k_before,KeyType k_after){
    RSet r;
    r=find_node(root,k_before);
    while(r.flag){
        r.node->data[r.pos]=k_after;
        r=find_node(root,k_before);
    }
}
//向左移一位
Status left_move_one(BTreePlus *node,int data_index,int child_index){
    if(!(*node))return 0;
    if(data_index<=0)data_index=1;
    if(child_index<=0)child_index=0;
    int i;
    for(i=data_index;i<(*node)->keynum;i++){
        (*node)->data[i]=(*node)->data[i+1];
    }
    for(i=child_index;i<(*node)->keynum;i++){
        (*node)->child[i]=(*node)->child[i+1];
    }
}
//向左移一位
Status left_move(RSet r){
    BTreePlus p=r.node,t;
    int i;
    if(r.pos<=0)i=p->keynum;
    for(i=r.pos;i<p->keynum;i++){
        p->data[i]=p->data[i+1];
    }
    if(r.null_child_index<=0)i=p->keynum;
    for(i=r.null_child_index;i<p->keynum;i++){
        p->child[i]=p->child[i+1];
    }
}
Status right_move(RSet r){
    BTreePlus p=r.node,t;
    int i;
    for(i=r.pos;i>1;i--){
        p->data[i]=p->data[i-1];
    }
    for(i=r.null_child_index;i>0;i--){
        p->child[i]=p->child[i-1];
    }
}
Status OrderByKey(RSet r) {
    int i, j,size;
    KeyType temp;
    BTreePlus p=r.node,t;
    size=p->keynum;
    for (j = 0; j < size - 1; j++)            // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (i = 0; i < size - 1 - j; i++)    // 依次比较相邻的两个元素,使较大的那个向后移
        {
            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            if (p->data[i+1] > p->data[i+2]) {
                /** exchange data**/
                temp = p->data[i+1];
                p->data[i+1] = p->data[i + 2];
                p->data[i + 2] = temp;
                /** exchange pointer**/
                t=p->child[i];
                p->child[i]=p->child[i+1];
                p->child[i+1]=t;
            }
        }
    }
}
Status delete_level_third(RSet res,BTreePlus *b){
    BTreePlus pnod=NULL,parent=NULL,leftChild=NULL, rightChild=NULL,ptmp=NULL;
    int min,max,index,i,j;
    min=MinKeyNum;
    max=MaxKeyNum;
    pnod=res.node;
    if(!pnod)return ERROR;
    /**
         * 情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子，K的右指针为空)即可使删除操作结束。
         * 删除后重新调整位置
         * */
    if(pnod->keynum > min){
        left_move(res);
        pnod->data[pnod->keynum]=KeyType_NULL;
        pnod->child[pnod->keynum]=NULL;
        pnod->keynum--;
    }else{
        /**
         * 情形二:
         * 若x->keynum=Min，该叶子中的关键字个数已是最小值，删K及其右指针后会破坏B-树的性质(3)。
         * 若*x的左(或右)邻兄弟结点*y中的关键字数目大于Min，则将*y中的最大(或最小)关键字上移至双亲结点*parent中，
         * 而将*parent中相应的关键字下移至x中
         * */
        Boolean bl=FALSE,br=FALSE;
        parent=pnod->parent;
        index=SearchPosition(parent,pnod->data[pnod->keynum]);
        //优先向左,then forward right
        if(index>=1){
            leftChild=parent->child[index-1];
            if(leftChild->keynum>min)bl=TRUE;
        }
        if(index<parent->keynum){
            rightChild=parent->child[index+1];
            if(rightChild->keynum>min)br=TRUE;
        }
        if(bl&&leftChild){
            right_move(res);
            pnod->data[1]=parent->data[index];
            pnod->child[0]=leftChild->child[leftChild->keynum];
            parent->data[index]=leftChild->data[leftChild->keynum];
            leftChild->data[leftChild->keynum]=KeyType_NULL;
            leftChild->child[leftChild->keynum]=NULL;
            leftChild->keynum--;
            //OrderByKey_(res);
            //如果删除f，等下验证,插入之后要进行排序
        }else if(br&&rightChild){
            left_move(res);
            pnod->data[pnod->keynum]=parent->data[index+1];
            pnod->child[pnod->keynum]=rightChild->child[0];
            parent->data[index+1]=rightChild->data[1];
            left_move_one(&rightChild,1,0);
            rightChild->data[rightChild->keynum]=KeyType_NULL;
            rightChild->child[rightChild->keynum]=NULL;
            rightChild->keynum--;
            //OrderByKey_(res);
        }else{
            /**情形三:**/
            //合并左结点优先，如左结点不符合条件合并右结点
            if((!bl)&&leftChild){
                leftChild->data[leftChild->keynum+1]=parent->data[index];
                leftChild->keynum++;
                //当前节点的元素逐个移到左节点，除被删除元素外
                j=leftChild->keynum;
                for(i=1;i<=pnod->keynum;i++){
                    if(res.pos==i)continue;//丢弃删除的元素，不迁移
                    leftChild->data[++leftChild->keynum]=pnod->data[i];
                }
                //迁移孩子
                for(i=0;i<=pnod->keynum;i++){
                    //丢弃的孩子不迁移
                    if(pnod->child[i]) {
                        pnod->child[i]->parent=leftChild;
                        leftChild->child[j++] = pnod->child[i];
                    }
                }
                res.pos=index;
            } else if((!br)&&rightChild){
                //腾出空位:腾出右节点的KEY,child,让父节点的KEY,child 和插入
                j=pnod->keynum+rightChild->keynum;
                for(i=0;i<rightChild->keynum;i++){
                    rightChild->data[j-i]=rightChild->data[rightChild->keynum-i];
                    rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                }
                rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                rightChild->data[pnod->keynum]=parent->data[index+1];
                //rightChild->child[pnod->keynum]=pnod->child[res.pos-1];
                rightChild->keynum++;
                //迁移元素
                for(i=1,j=1;j<=pnod->keynum;i++,j++){
                    //丢弃删除的元素，不迁移
                    if(res.pos!=j){
                        rightChild->data[i]=pnod->data[j];
                        rightChild->keynum++;
                    }else{
                        i--;
                    }
                }
                //迁移孩子
                for(i=0,j=0;j<=pnod->keynum;i++,j++){
                    //丢弃的孩子不迁移
                    if(pnod->child[j]){
                        pnod->child[j]->parent=rightChild;
                        rightChild->child[i]=pnod->child[j];
                    }else{
                        i--;
                    }
                }
                res.pos=index+1;
            }
            //置空,释放节点
            printf("%c\n",pnod->data[1]);
            parent->child[index]=NULL;
            pfree(pnod);
            if((!parent->parent)&&parent->keynum-1<=0){
                ptmp=parent;
                if((!bl)&&leftChild){
                    leftChild->parent=NULL;
                    parent=leftChild;
                }
                if((!br)&&rightChild){
                    rightChild->parent=NULL;
                    parent=rightChild;
                }
                printf("%c\n",ptmp->data[1]);
                pfree(ptmp);
                *b=parent;
                return 1;
            }
            res.null_child_index=index;
            res.node=parent;
            res.flag=1;
            delete_level_third(res,b);
        }
    }
    return 1;
}

Status delete_level_second(RSet res,BTreePlus *b){
    BTreePlus pnod=NULL,parent=NULL,leftChild=NULL, rightChild=NULL,ptmp=NULL,child,pre_node,next_node;
    int min,max,index,i,j,neighbor_num;
    KeyType keytmp,keytpm2;
    ResKey rek;
    RSet rs1,rs2;
    min=MinKeyNum;
    max=MaxKeyNum;
    pnod=res.node;
    if(!pnod)return ERROR;
    rek=next_key(pnod,res.pos);
    keytmp=pnod->data[res.pos];
    parent=pnod->parent;
    child=pnod->child[0];
    if(!child)child=pnod->child[1];
    index=SearchPosition(parent,pnod->data[pnod->keynum]);
    /**
         * 情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子)即可使，如果K属于非叶子节点的索引，取K的后继元素代替之，删除操作结束。
         * 删除后重新调整位置
         * */
    if(pnod->keynum > min){
        //向左移一位
        left_move(res);
        pnod->data[pnod->keynum]=KeyType_NULL;
        pnod->child[pnod->keynum]=NULL;
        pnod->keynum--;
        adjust_node_index(&pnod,res.pos-1);
    }else{
        /**
         * 情形二: 情形2： 若x->keynum=Min，如左或右兄弟Keynum>Min,借一个填充K，
         * 如果K同时作为非父节点的索引元素，用新的K值并取代其索引元素；
         * 如果因此父节点的索引被打乱，则索引元素重排。如果该节点是索引节点，孩子一同过继。
         * */
        Boolean bl=FALSE,br=FALSE;
        //优先向左,then forward right
        if(index>=1){
            leftChild=parent->child[index-1];
            if(leftChild->keynum>min)bl=TRUE;
        }
        if(index<parent->keynum){
            rightChild=parent->child[index+1];
            if(rightChild->keynum>min)br=TRUE;
        }
        if(bl&&leftChild){
            keytpm2=leftChild->data[leftChild->keynum];
            right_move(res);
            pnod->data[1]=leftChild->data[leftChild->keynum];
            pnod->child[0]=leftChild->child[leftChild->keynum];
            leftChild->data[leftChild->keynum]=KeyType_NULL;
            leftChild->child[leftChild->keynum]=NULL;
            leftChild->keynum--;
            //这里需要优化，不需要全部排序，只需要部分排序
            //OrderByKey(res);
            //这步可能是多多余的，因为节点的最后一个元素似乎不可能出现在索引节点的元素中，因为取后继元素为替换者.注：本树取最小的作为父节点元素
            //replace_key(*b,keytmp,keytpm2);
            //父节点的索引被打乱，则索引元素重新取该元素对应的孩子的最小元素
            pnod->data[1]=pnod->child[1]->data[1];
            //如果删除f，等下验证,插入之后要进行排序
            pnod->data[0]=KeyType_NULL;
            //第2次递归调用,调整索引
            rs1=find_next_key(parent,index);
            parent->data[index]=rs1.node->data[rs1.pos];
            if(index+1<=parent->keynum){
                rs2=find_next_key(parent,index+1);
                parent->data[index+1]=rs2.node->data[rs2.pos];
            }
        }else if(br&&rightChild){
            left_move(res);
            pnod->data[pnod->keynum]=rightChild->data[1];
            pnod->child[pnod->keynum]=rightChild->child[0];
            left_move_one(&rightChild,1,0);
            rightChild->data[rightChild->keynum]=KeyType_NULL;
            rightChild->child[rightChild->keynum]=NULL;
            rightChild->keynum--;
            //父节点的索引被打乱，则索引元素重新取该元素对应的孩子的最小元素
            adjust_node_index(&pnod,1);
            pnod->data[0]=KeyType_NULL;
            //第2次递归调用,后继元素替换索引
            rs1=find_next_key(parent,index);
            parent->data[index]=rs1.node->data[rs1.pos];
            if(index+1<=parent->keynum){
                rs2=find_next_key(parent,index+1);
                parent->data[index+1]=rs2.node->data[rs2.pos];
            }
        }else{
            /**情形三:**/
            //合并左结点优先，如左结点不符合条件合并右结点
            if((!bl)&&leftChild){
                neighbor_num=leftChild->keynum;
                leftChild->data[leftChild->keynum+1]=parent->data[index];
                leftChild->keynum++;

                //当前节点的元素逐个移到左节点，除被删除元素外
                j=leftChild->keynum;
                for(i=1;i<=pnod->keynum;i++){
                    if(res.pos==i)continue;//丢弃删除的元素，不迁移
                    leftChild->data[++leftChild->keynum]=pnod->data[i];
                }
                //迁移孩子
                for(i=0;i<=pnod->keynum;i++){
                    //丢弃的孩子不迁移
                    if(pnod->child[i]) {
                        pnod->child[i]->parent=leftChild;
                        leftChild->child[j++] = pnod->child[i];
                    }
                }
                //第2次递归调用,调整索引
                adjust_node_index(&leftChild,neighbor_num);
                //leftChild->data[neighbor_num+res.pos]=leftChild->child[neighbor_num+res.pos]->data[1];
                //leftChild->data[neighbor_num+res.pos+1]=leftChild->child[neighbor_num+res.pos+1]->data[1];
                res.pos=index;
            } else if((!br)&&rightChild){
                neighbor_num=rightChild->keynum;
                //腾出空位:腾出右节点的KEY,child,让父节点的KEY,child 和插入
                j=pnod->keynum+rightChild->keynum;
                for(i=0;i<rightChild->keynum;i++){
                    rightChild->data[j-i]=rightChild->data[rightChild->keynum-i];
                    rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                }
                rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                rightChild->data[pnod->keynum]=parent->data[index+1];
                rightChild->keynum++;
                //迁移元素
                for(i=1,j=1;j<=pnod->keynum;i++,j++){
                    //丢弃删除的元素，不迁移
                    if(res.pos!=j){
                        rightChild->data[i]=pnod->data[j];
                        rightChild->keynum++;
                    }else{
                        i--;
                    }
                }
                //迁移孩子
                for(i=0,j=0;j<=pnod->keynum;i++,j++){
                    //丢弃的孩子不迁移
                    if(pnod->child[j]){
                        pnod->child[j]->parent=rightChild;
                        rightChild->child[i]=pnod->child[j];
                    }else{
                        i--;
                    }
                }
                //第2次递归调用,调整索引
                adjust_node_index(&rightChild,neighbor_num);
                res.pos=index+1;
            }
            //置空,释放节点
            printf("%c\n",pnod->data[1]);
            parent->child[index]=NULL;
            pfree(pnod);
            if((!parent->parent)&&parent->keynum-1<=0){
                ptmp=parent;
                if((!bl)&&leftChild){
                    leftChild->parent=NULL;
                    parent=leftChild;
                }
                if((!br)&&rightChild){
                    rightChild->parent=NULL;
                    parent=rightChild;
                }
                printf("%c\n",ptmp->data[1]);
                pfree(ptmp);
                *b=parent;
                return 1;
            }
            res.node=parent;
            res.flag=1;
            //BTreePlus_print(*b,1);
            delete_level_third(res,b);
        }
    }
}
Status delete_leaf_first(RSet res,BTreePlus *b){
    BTreePlus pnod=NULL,parent=NULL,leftChild=NULL, rightChild=NULL,ptmp=NULL,child,pre_node,next_node;
    int min,max,index,i,j,neighbor_num;
    KeyType keytmp,keytpm2;
    ResKey rek;
    RSet rs1,rs2;
    min=MinKeyNum;
    max=MaxKeyNum;
    pnod=res.node;
    if(!pnod)return ERROR;
    rek=next_key(pnod,res.pos);
    keytmp=pnod->data[res.pos];
    parent=pnod->parent;
    child=pnod->child[0];
    if(!child)child=pnod->child[1];
    index=SearchPosition(parent,pnod->data[pnod->keynum]);
    /**
         * 情形一：若x->keynum>Min，则只需删去K及其右指针(*x是叶子)即可使，如果K属于非叶子节点的索引，取K的后继元素代替之，删除操作结束。
         * 删除后重新调整位置
         * */
    if(pnod->keynum > min){
        left_move(res);
        pnod->data[pnod->keynum]=KeyType_NULL;
        pnod->child[pnod->keynum]=NULL;
        pnod->keynum--;
        if(rek.flag)replace_key(*b,keytmp,rek.key);

        parent->data[index]=parent->child[index]->data[1];
        parent->data[0]=KeyType_NULL;
        // 这个函数注释掉，时间代价太大
        //adjust_parent_index(&pnod->parent);
    }else{
        /**
         * 情形二: 情形2： 若x->keynum=Min，如左或右兄弟Keynum>Min,借一个填充K，
         * 如果K同时作为非父节点的索引元素，用新的K值并取代其索引元素；
         * 如果因此父节点的索引被打乱，则索引元素重排。如果该节点是索引节点，孩子一同过继。
         * */
        Boolean bl=FALSE,br=FALSE;
        //优先向左,then forward right
        if(index>=1){
            leftChild=parent->child[index-1];
            if(leftChild->keynum>min)bl=TRUE;
        }
        if(index<parent->keynum){
            rightChild=parent->child[index+1];
            if(rightChild->keynum>min)br=TRUE;
        }
        if(bl&&leftChild){
            keytpm2=leftChild->data[leftChild->keynum];
            pnod->data[res.pos]=leftChild->data[leftChild->keynum];

            leftChild->data[leftChild->keynum]=KeyType_NULL;
            leftChild->child[leftChild->keynum]=NULL;
            leftChild->keynum--;
            //这里需要优化，不需要全部排序，只需要部分排序
            OrderByKey(res);
            //这步可能是多多余的，因为节点的最后一个元素似乎不可能出现在索引节点的元素中，注：本树取最小的作为父节点元素
            replace_key(*b,keytmp,keytpm2);
            //父节点的索引被打乱，则索引元素重新取该元素对应的孩子的最小元素
            parent->data[index]=parent->child[index]->data[1];
            //如果删除f，等下验证,插入之后要进行排序
            parent->data[0]=KeyType_NULL;

        }else if(br&&rightChild){
            pnod->data[res.pos]=rightChild->data[1];
            for(i=1;i<rightChild->keynum;i++){
                rightChild->data[i]=rightChild->data[i+1];
                rightChild->child[i-1]=rightChild->child[i];
            }
            rightChild->data[rightChild->keynum]=KeyType_NULL;
            rightChild->child[rightChild->keynum]=NULL;
            rightChild->keynum--;
            OrderByKey(res);
            keytpm2=pnod->data[res.pos];
            replace_key(*b,keytmp,keytpm2);
            //父节点的索引被打乱，则索引元素重新取该元素对应的孩子的最小元素
            parent->data[index]=parent->child[index]->data[1];
            parent->data[index+1]=parent->child[index+1]->data[1];
            parent->data[0]=KeyType_NULL;
        }else{
            /**情形三:**/
            //合并左结点优先，如左结点不符合条件合并右结点
            if((!bl)&&leftChild){
                //当前节点的元素逐个移到左节点，除被删除元素外
                j=leftChild->keynum;
                for(i=1;i<=pnod->keynum;i++){
                    if(res.pos==i)continue;//丢弃删除的元素，不迁移
                    leftChild->data[++leftChild->keynum]=pnod->data[i];
                }
                //迁移孩子
                for(i=0;i<=pnod->keynum;i++){
                    //丢弃的孩子不迁移
                    if(pnod->child[i]) {
                        pnod->child[i]->parent=leftChild;
                        leftChild->child[++j] = pnod->child[i];
                    }
                }
                res.pos=index;
            } else if((!br)&&rightChild){
                //腾出空位:腾出右节点的KEY,child,让父节点的KEY,child 和插入
                j=pnod->keynum+rightChild->keynum-1;
                for(i=0;i<rightChild->keynum;i++){
                    rightChild->data[j-i]=rightChild->data[rightChild->keynum-i];
                    rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                }
                rightChild->child[j-i]=rightChild->child[rightChild->keynum-i];
                //迁移元素
                for(i=1,j=1;j<=pnod->keynum;i++,j++){
                    //丢弃删除的元素，不迁移
                    if(res.pos!=j){
                        rightChild->data[i]=pnod->data[j];
                        rightChild->keynum++;
                    }else{
                        i--;
                    }
                }
                //迁移孩子
                for(i=0,j=0;j<=pnod->keynum;i++,j++){
                    //丢弃的孩子不迁移
                    if(pnod->child[j]){
                        pnod->child[j]->parent=rightChild;
                        rightChild->child[i]=pnod->child[j];
                    }else{
                        i--;
                    }
                }
                res.pos=index+1;
            }
            pre_node=pnod->prev;
            next_node=pnod->next;
            if(next_node)next_node->prev=pre_node;
            else pre_node->next=NULL;
            if(pre_node)pre_node->next=pnod->next;
            else next_node->prev=NULL;
            //置空,释放节点
            printf("%c\n",pnod->data[1]);
            parent->child[index]=NULL;
            pfree(pnod);
            if((!parent->parent)&&parent->keynum-1<=0){
                ptmp=parent;
                if((!bl)&&leftChild){
                    leftChild->parent=NULL;
                    parent=leftChild;
                }
                if((!br)&&rightChild){
                    rightChild->parent=NULL;
                    parent=rightChild;
                }
                printf("%c\n",ptmp->data[1]);
                pfree(ptmp);
                *b=parent;
                return 1;
            }
            res.null_child_index=index;
            res.node=parent;
            res.flag=1;
            //BTreePlus_print(*b,1);
            delete_level_second(res,b);
        }
    }
}
/**
 * @param b the tree
 * @param k the key
 * @return
 */
Status delete_bplustree(BTreePlus *b, KeyType k){
    RSet res,r2;
    BTreePlus p,pnod=NULL,parent=NULL,leftChild=NULL, rightChild=NULL;
    int min,max,index,i,j;
    min=MinKeyNum;
    max=MaxKeyNum;
    p=*b;
    if(!p)return ERROR;
    KeyType keytmp,keytpm2;
    res.pos=-1;
    res.null_child_index=-1;
    res.flag=-1;
    res=find_leaf(p,k);
    if(!res.flag)return FALSE;
    pnod=res.node;

    delete_leaf_first(res,b);

}
/*-----------------------------------------Insert--------------------------------------------*/
//插入一个key，n+1是真正插入的位置
void InsertK(BTreePlus *t, KeyType k, int n) {
    BTreePlus p;
    int i;
    p = *t;
    for (i = max_degree - 1; i > n; i--) {
        p->data[i + 1] = p->data[i];
    }
    p->data[n + 1] = k;
    p->keynum++;
}
//插入一个key，实现上调用了InsertK()
void Insert_(BTreePlus *t, KeyType k) {
    int position;
    position = SearchPosition(*t, k);
    InsertK(t, k, position);
}
//创建一个新的节点，初始化新节点
void NewNode_(BTreePlus *node, KeyType k) {
    int i;
    (*node) = palloc(sizeof(BTNodePlus));
    (*node)->keynum = 1;
    (*node)->data[1] = k;
    (*node)->parent = NULL;
    (*node)->next = NULL;
    (*node)->prev = NULL;
    (*node)->is_leaf = FALSE;
    for (i = 0; i < max_degree + 1; i++)
        (*node)->child[i] = NULL;
}
//根分裂，如果符合再分裂的条件递归之
void split_root(BTreePlus *t) {
    BTreePlus parent, node, p;
    int i,j, s = MiddleKey;
    p = *t;
    // if a new root
    if (!p->parent) {
        NewNode_(&parent, p->data[s]);
        NewNode_(&node, p->data[s + 1]);
        p->parent = parent;
        node->parent = parent;
        parent->child[0] = p;
        parent->child[1] = node;
    } else {
        parent = p->parent;
        Insert_(&parent, p->data[s]);
        //
        NewNode_(&node, p->data[s + 1]);
        node->parent = parent;
        i=SearchPosition(parent,p->data[p->keynum]);
        for (j=parent->keynum; j>i; j--) {
            parent->child[j]=parent->child[j-1];
        }
        parent->child[i] = node;

    }
    //把m+1/2右边的key搬到右边的新节点中，同时左边该key置空，numkey为s-1
    for (i = s + 2;i <= p->keynum; i++) {
        //move key to new node,then set null
        Insert_(&node, p->data[i]);
        p->data[i]=KeyType_NULL;

    }
    //move pointer to new node,then set null
    if(p->child[0]){
        for(i=s,j=0;i<=p->keynum;j++,i++){
            //Belong to new daddy
            p->child[i]->parent=node;
            node->child[j]=p->child[i];
            p->child[i]=NULL;
        }
    }
    p->data[s]=KeyType_NULL;
    p->data[s+1]=KeyType_NULL;
    p->keynum=s-1;
    //如果父节点满了，递归之
    if (parent->keynum >= max_degree)
        split_root(&parent);
}
//叶子分裂，如果符合再分裂的条件递归之
void split_leaf(BTreePlus *t) {
    BTreePlus parent, node,p,next_node,prev_node;
    int i,j, s = MiddleKey;
    p = *t;
    // if a new root
    if (!p->parent) {
        NewNode_(&parent, p->data[s]);
        NewNode_(&node, p->data[s]);
        //link parent  pointer
        p->parent = parent;
        node->parent = parent;
        //link pre pointer
        node->prev=p;
        if(p->next)p->next->prev=node;
        //link next pointer
        node->next=p->next;
        p->next=node;
        //link child pointer
        parent->child[0] = p;
        parent->child[1] = node;
        // add flag of leaf
        if(p->is_leaf)node->is_leaf=TRUE;
    } else {
        parent = p->parent;
        Insert_(&parent, p->data[s]);
        NewNode_(&node, p->data[s]);
        //link pre pointer
        node->prev=p;
        if(p->next)p->next->prev=node;
        //link next pointer
        node->next=p->next;
        p->next=node;
        //link parent  pointer
        node->parent = parent;
        i=SearchPosition(parent,p->data[p->keynum]);
        for (j=parent->keynum; j>i; j--) {
            parent->child[j]=parent->child[j-1];
        }
        //link pointer of child
        parent->child[i] = node;
        // add flag of leaf
        if(p->is_leaf)node->is_leaf=TRUE;
    }
    // writing here....
    //把m+1/2右边的key搬到右边的新节点中，同时左边该key置空，numkey为s-1
    for (i = s+1;i <= p->keynum; i++) {
        //move key to new node,then set null
        Insert_(&node, p->data[i]);
        p->data[i]=KeyType_NULL;

    }
    //move pointer to new node,then set null
    if(p->child[0]){
        for(i=s,j=0;i<=p->keynum;j++,i++){
            //Belong to new daddy
            p->child[i]->parent=node;
            node->child[j]=p->child[i];
            p->child[i]=NULL;
        }
    }
    p->data[s]=KeyType_NULL;
    //p->data[s+1]=KeyType_NULL;
    p->keynum=s-1;
    //如果父节点满了，再分裂
    if (parent->keynum >= max_degree)
        split_root(&parent);
}
Status InsertBTree_(BTreePlus *t, KeyType k) {
    int i = 0, s = 0;
    BTreePlus p;
    RSet r;
    // if tree is null,insert first key
    if (!(*t)) {
        NewNode_(t, k);
        (*t)->is_leaf=TRUE;
        return OK;
    } else {
        r = find_node(*t, k);
        if (r.flag == 1)return Repetition;
        else if (r.flag == 0) {
            InsertK(&r.node, k, r.pos);
            if (r.node->keynum >= max_degree) {
                split_leaf(&r.node);
                //如有下次插入，须从根节点开始
                p = r.node;
                while(p->parent)
                    p=p->parent;
                *t=p;
            }
        }
        return  OK;
    }

}
/*-----------------------------------------Print BTreePlus--------------------------------------------*/
// 按层次打印 B 树
/**
 *  layer init is 1
 */
void BTreePlus_print(BTreePlus tree, int layer)
{
    int i;
    BTNodePlus *node = tree;

    if (node) {
        //display layer by space key
        for(i=1;i<layer;i++){
            printf("%c",' ');
            printf("%c",' ');
            printf("%c",' ');
        }

        printf("第 %d 层， %d node : ", layer, node->keynum);

        //打印出结点中的全部元素，方便调试查看keynum之后的元素是否为0(即是否存在垃圾数据)；而不是keynum个元素。
        for (i = 1; i <=node->keynum; ++i) {
            //for (i = 0; i < node->keynum; ++i) {
            printf("%c ", node->data[i]);
        }
        printf("\n");
        ++layer;
        for (i = 0 ; i <= node->keynum; i++) {
            if (node->child[i]) {
                BTreePlus_print(node->child[i], layer);
            }
        }
    }
    else {
        printf("树为空。\n");
    }
}
int BTreePlus_Main() {
    int num=21;
    //char r[17] = {'C','G','L','N','Q','M','T','D','P','R','H','J','K','I','F','A','B'};
    char r[21] = {'C', 'N', 'G', 'A', 'H', 'E', 'K', 'Q', 'M', 'F', 'W', 'L', 'T', 'Z', 'D', 'P', 'R', 'X', 'Y', 'S','B'};
    //char r[20] = {'a','g','f','b','k','d','h','m','j','e','s','i','r','x','c','l','n','t','u','p'};
    //char r[14] = {'p','e','h','m','t','x','b','d','f','g','i','k','l','j'};
    //char r[16] = {'p','e','h','m','t','x','b','d','f','g','i','k','l','j','s','o'};
    //char r[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    BTreePlus T = NULL;
    Status s;
    int i;
    for (i = 0; i < num; i++) {
        //printf("insert : %c\n",r[i]);
        s=InsertBTree_(&T, r[i]);
    }
    BTreePlus_print(T,1);
    printf("delete : %c\n",'D');
    delete_bplustree(&T,'D');
    BTreePlus_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'E');
    delete_bplustree(&T,'E');
    BTreePlus_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'C');
    delete_bplustree(&T,'C');
    BTreePlus_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'B');
    delete_bplustree(&T,'B');
    BTreePlus_print(T,1);
    /**---------------------------------**/
    printf("delete : %c\n",'g');
    delete_bplustree(&T,'g');
    BTreePlus_print(T,1);
    /**---------------------------------**/
    //printf("delete : %c\n",'k');
    //delete_bplustree(&T,'k');
    //BTreePlus_print(T,1);
    /**---------------------------------**/
    //printf("delete : %c\n",'m');
    //delete_bplustree(&T,'m');
    //BTreePlus_print(T,1);
    return 0;
}